{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Unique Characters of All Substrings of a Given String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: uniqueLetterString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计子串中的唯一字符"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们定义了一个函数 <code>countUniqueChars(s)</code> 来统计字符串 <code>s</code> 中的唯一字符，并返回唯一字符的个数。</p>\n",
    "\n",
    "<p>例如：<code>s = \"LEETCODE\"</code> ，则其中 <code>\"L\"</code>, <code>\"T\"</code>,<code>\"C\"</code>,<code>\"O\"</code>,<code>\"D\"</code> 都是唯一字符，因为它们只出现一次，所以 <code>countUniqueChars(s) = 5</code> 。</p>\n",
    "\n",
    "<p>本题将会给你一个字符串 <code>s</code> ，我们需要返回 <code>countUniqueChars(t)</code> 的总和，其中 <code>t</code> 是 <code>s</code> 的子字符串。输入用例保证返回值为&nbsp;32 位整数。</p>\n",
    "\n",
    "<p>注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 <code>s</code> 的所有子字符串中的唯一字符）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = \"ABC\"\n",
    "<strong>输出: </strong>10\n",
    "<strong>解释:</strong> 所有可能的子串为：\"A\",\"B\",\"C\",\"AB\",\"BC\" 和 \"ABC\"。\n",
    "     其中，每一个子串都由独特字符构成。\n",
    "     所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = \"ABA\"\n",
    "<strong>输出: </strong>8\n",
    "<strong>解释: </strong>除了 countUniqueChars(\"ABA\") = 1 之外，其余与示例 1 相同。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"LEETCODE\"\n",
    "<strong>输出：</strong>92\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 只包含大写英文字符</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-unique-characters-of-all-substrings-of-a-given-string](https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-unique-characters-of-all-substrings-of-a-given-string](https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ABC\"', '\"ABA\"', '\"LEETCODE\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        ans,a,pre,ppre = 0,0,{},{}\n",
    "        for i,x in enumerate(s):\n",
    "            a += i-pre.get(s[i],-1) #s[i]不重复的子串数\n",
    "            a -= pre.get(s[i],-1)+1 #s[i]重复的子串数\n",
    "            a += ppre.get(s[i],-1)+1 #pre[s[i]]已经计算过的\n",
    "\n",
    "            ans += a\n",
    "            ppre[s[i]] = pre.get(s[i],-1)\n",
    "            pre[s[i]] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        ans,a,pre,ppre = 0,0,{},{}\n",
    "        for i,x in enumerate(s):\n",
    "            a += i-pre.get(s[i],-1) #s[i]不重复的子串数\n",
    "            a -= pre.get(s[i],-1)+1 #s[i]重复的子串数\n",
    "            a += ppre.get(s[i],-1)+1 #pre[s[i]]已经计算过的\n",
    "\n",
    "            ans += a\n",
    "            ppre[s[i]] = pre.get(s[i],-1)\n",
    "            pre[s[i]] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        ans = total = 0\n",
    "        last0,last1 = {},{}\n",
    "        for i,c in enumerate(s):\n",
    "            total += i-2*last0.get(c,-1)+last1.get(c,-1)\n",
    "            ans += total\n",
    "            last1[c] = last0.get(c,-1)\n",
    "            last0[c] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        ans = total = 0\n",
    "        last0, last1 = {}, {}\n",
    "        for i, c in enumerate(s):\n",
    "            total += i - 2 * last0.get(c, -1) + last1.get(c, -1)\n",
    "            ans += total\n",
    "            last1[c] = last0.get(c, -1)\n",
    "            last0[c] = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        pre = {}\n",
    "        pre_pre = {}\n",
    "        for i,x in enumerate(s):\n",
    "            cur += (i - pre.get(x,-1)) - (pre.get(x,-1) - pre_pre.get(x,-1))\n",
    "            ans += cur\n",
    "            pre_pre[x] = pre.get(x,-1)\n",
    "            pre[x] = i\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        ans,a,pre,ppre = 0,0,{},{}\n",
    "        for i,x in enumerate(s):\n",
    "            a += i-2*pre.get(s[i],-1)+ppre.get(s[i],-1)\n",
    "            ans += a\n",
    "            ppre[s[i]] = pre.get(s[i],-1)\n",
    "            pre[s[i]] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        ans = total = 0\n",
    "        last0, last1 = {}, {}\n",
    "        for i, c in enumerate(s):\n",
    "            total += i - 2 * last0.get(c, -1) + last1.get(c, -1)\n",
    "            ans += total\n",
    "            last1[c] = last0.get(c, -1)\n",
    "            last0[c] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        res ,total = 0, 0\n",
    "        d1, d2 = {}, {}\n",
    "        for i, c in enumerate(s):\n",
    "            total += i - 2 * d1.get(c, -1) + d2.get(c, -1)\n",
    "            res += total\n",
    "            d2[c] = d1.get(c, -1)\n",
    "            d1[c] = i\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        last_seen = dict()\n",
    "        last_2_seen = dict()\n",
    "        res = 0\n",
    "        for c in string.ascii_uppercase:\n",
    "            last_2_seen[c] = -1\n",
    "            last_seen[c] = -1\n",
    "        for i in range(n):\n",
    "            last_2_seen[s[i]] = last_seen[s[i]]\n",
    "            last_seen[s[i]] = i\n",
    "            for c in string.ascii_uppercase:\n",
    "                res += last_seen[c]-last_2_seen[c]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        mp = defaultdict(list)\n",
    "        res = 0\n",
    "        ans = 0\n",
    "        # 1 2 3 3 4 3\n",
    "        # 1 / / / / /     1 = 1\n",
    "        # 2 1 / / / /     3 = 2 + 1\n",
    "        # 3 2 1 / / /     6 = 3 + 2 + 1\n",
    "        # 2 1 0 1 / /     5 = 2 + 1 + 0 + 1\n",
    "        # 3 2 1 2 1 /     9 = 3 + 2 + 1 + 2 + 1  # 不在里面 加 i + 1\n",
    "        # 3 2 1 1 2 1     10 = 3 + 2 + 1 + (2 - 1) + (1 + 1) + 1  # 在里面  设次近的一个二为 x 最近的为 y  减 y - x  加 i - y - 1 + 1\n",
    "        # 1 2 3 2 3 2 \n",
    "        # 1 / / / / /\n",
    "        # 2 1 / / / /\n",
    "        # 3 2 1 / / /\n",
    "        # 2 1 2 1 / /\n",
    "        # 1 0 1 2 1 /\n",
    "        # 1 0 0 1 2 1\n",
    "        for i, c in enumerate(s):\n",
    "            res += i - mp[c][1] - 1 + 1 - mp[c][1] + mp[c][0] if c in mp else i + 1\n",
    "            ans += res\n",
    "            mp[c] = [mp[c][1], i] if c in mp else [-1, i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        tmp = [[-1, -1] for _ in range(26)]  # 记录上两个字符出现的位置\n",
    "\n",
    "        ans = prev = 0  # prev为滚动变量，表示上一个字符的贡献\n",
    "        for idx, ch in enumerate(s):\n",
    "            i = ord(ch) - 65\n",
    "            if tmp[i][0] < 0:  # 之前没出现过该字符，dp[i]=dp[i-1]+idx+1\n",
    "                prev += idx + 1\n",
    "            elif tmp[i][1] < 0:  # 之前出现过一次该字符，直到该字符的位置贡献全+1，但到上次出现字符之前的位置贡献全-1\n",
    "                prev += idx - 2 * tmp[i][0] - 1\n",
    "            else:  # 之前出现过两次该字符，在前两个字符之前的位置贡献不需要-1\n",
    "                prev += idx - 2 * tmp[i][0] + tmp[i][1]\n",
    "            ans += prev\n",
    "            tmp[i][1], tmp[i][0] = tmp[i][0], idx\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        ans = total = 0\n",
    "        last0, last1 = {}, {}\n",
    "        for i, c in enumerate(s):\n",
    "            total += i - 2 * last0.get(c, -1) + last1.get(c, -1)\n",
    "            ans += total\n",
    "            last1[c] = last0.get(c, -1)\n",
    "            last0[c] = i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        ans,a,pre,ppre = 0,0,{},{}\n",
    "        for i,x in enumerate(s):\n",
    "            a += i-pre.get(s[i],-1)\n",
    "            a -= pre.get(s[i],-1)+1\n",
    "            a += ppre.get(s[i],-1)+1\n",
    "\n",
    "            ans += a\n",
    "            ppre[s[i]] = pre.get(s[i],-1)\n",
    "            pre[s[i]] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        mp = defaultdict(list)\n",
    "        res = 0\n",
    "        ans = 0\n",
    "        # 1 2 3 3 4 3\n",
    "        # 1 / / / / /     1 = 1\n",
    "        # 2 1 / / / /     3 = 2 + 1\n",
    "        # 3 2 1 / / /     6 = 3 + 2 + 1\n",
    "        # 2 1 0 1 / /     5 = 2 + 1 + 0 + 1\n",
    "        # 3 2 1 2 1 /     9 = 3 + 2 + 1 + 2 + 1  # 不在里面 加 i + 1\n",
    "        # 3 2 1 1 2 1     10 = 3 + 2 + 1 + (2 - 1) + (1 + 1) + 1  # 在里面  设次近的一个二为 x 最近的为 y  减 y - x  加 i - y - 1 + 1\n",
    "        # 1 2 3 2 3 2 \n",
    "        # 1 / / / / /\n",
    "        # 2 1 / / / /\n",
    "        # 3 2 1 / / /\n",
    "        # 2 1 2 1 / /\n",
    "        # 1 0 1 2 1 /\n",
    "        # 1 0 0 1 2 1\n",
    "        for i, c in enumerate(s):\n",
    "            res += i - mp[c][1] - 1 + 1 - mp[c][1] + mp[c][0] if c in mp else i + 1\n",
    "            ans += res\n",
    "            if c in mp:\n",
    "                mp[c] = [mp[c][1], i]\n",
    "            else:\n",
    "                mp[c] = [-1, i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "s[i - 1]结尾到s[i]结尾\n",
    "s[i] = c\n",
    "考虑到上个c的最后位置j 和倒数第二个位置k\n",
    ".....k.....j.....i\n",
    ".....c.....c.....i\n",
    "s[k+1,i-1]s[k+2,i-1]...s[j,i-1], 添加s[i], 每个结果都会-1  (共j-k个)\n",
    "s[j+1,i-1]s[j+1,i-1]....s[i-1,i-1], 添加s[i], 每个结果都会+1 (共i-j-1)\n",
    "还有单独s[i]一个字符\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        mp = Counter()\n",
    "        ans = sum = 0\n",
    "        for i, c in enumerate(s):\n",
    "            j, k = mp.get(c, (-1, -1))\n",
    "            sum += (i - j) - (j - k)\n",
    "            ans += sum\n",
    "            mp[c] = (i, j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "s[i - 1]结尾到s[i]结尾\n",
    "s[i] = c\n",
    "考虑到上个c的最后位置j 和倒数第二个位置k\n",
    ".....k.....j.....i\n",
    ".....c.....c.....i\n",
    "s[k+1,i-1]s[k+2,i-1]...s[j,i-1], 添加s[i], 每个结果都会-1  (共j-k个)\n",
    "s[j+1,i-1]s[j+1,i-1]....s[i-1,i-1], 添加s[i], 每个结果都会+1 (共i-j-1)\n",
    "还有单独s[i]一个字符\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        c1 = Counter()\n",
    "        c2 = Counter()\n",
    "        ans = sum = 0\n",
    "        for i, c in enumerate(s):\n",
    "            j, k = c1.get(c, -1), c2.get(c, -1)\n",
    "            sum += (i - j) - (j - k)\n",
    "            ans += sum\n",
    "            c1[c] = i\n",
    "            c2[c] = j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        last = {chr(c+ ord('A')):[-1,-1] for c in range(26)}\n",
    "\n",
    "        ans = 0\n",
    "        dp = 0\n",
    "\n",
    "        for i, c in enumerate(s):\n",
    "            if last[c][0] > -1:\n",
    "                if last[c][1] > -1:\n",
    "                    dp += (i - last[c][0]) # 增加c到上一个c之间的独特数\n",
    "                    dp -= (last[c][0] - last[c][1])\n",
    "                    \n",
    "                else: # 前面只有一个这个字符\n",
    "                    dp -= (last[c][0] + 1) # 取消前一个字符在上一次c之前的独特数\n",
    "                    dp += (i - last[c][0]) # 增加c到上一个c之间的独特数\n",
    "            else:\n",
    "                dp += (1 + i)\n",
    "\n",
    "            last[c][1] = last[c][0]\n",
    "            last[c][0] = i\n",
    "            ans += dp\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        for c in range(ord('A'), ord('Z') + 1):\n",
    "            l = -1\n",
    "            r = -1\n",
    "            for i in range(n):\n",
    "                if s[i] == chr(c):\n",
    "                    l = r\n",
    "                    r = i\n",
    "                res += r - l\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        tmp = [[-1, -1] for _ in range(26)]  # 记录上两个字符出现的位置\n",
    "\n",
    "        ans = prev = 0\n",
    "        for idx, ch in enumerate(s):\n",
    "            i = ord(ch) - 65\n",
    "            if tmp[i][0] < 0:\n",
    "                prev += idx + 1\n",
    "            elif tmp[i][1] < 0:\n",
    "                prev += idx - 2 * tmp[i][0] - 1\n",
    "            else:\n",
    "                prev = prev + idx - 2 * tmp[i][0] + tmp[i][1]\n",
    "            ans += prev\n",
    "            tmp[i][1] = tmp[i][0]\n",
    "            tmp[i][0] = idx\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        ans,sumG,last,last1=0,0,{},{}\n",
    "        for i,c in enumerate(s):\n",
    "            if c in last:\n",
    "                j,k=last[c],last1[c]\n",
    "                sumG+=-(j-k)+i-j\n",
    "            else:\n",
    "                sumG+=i+1\n",
    "            ans+=sumG\n",
    "            last1[c]=last.get(c,-1)\n",
    "            last[c]=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "s[i - 1]结尾到s[i]结尾\n",
    "s[i] = c\n",
    "考虑到上个c的最后位置j 和倒数第二个位置k\n",
    ".....k.....j.....i\n",
    ".....c.....c.....i\n",
    "s[k+1,i-1]s[k+2,i-1]...s[j,i-1], 添加s[i], 每个结果都会-1  (共j-k个)\n",
    "s[j+1,i-1]s[j+1,i-1]....s[i-1,i-1], 添加s[i], 每个结果都会+1 (共i-j-1)\n",
    "还有单独s[i]一个字符\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        mp = Counter()\n",
    "        ans = sum = 0\n",
    "        for i, c in enumerate(s):\n",
    "            j, k = mp.get(c, [-1, -1])\n",
    "            sum += (i - j) - (j - k)\n",
    "            ans += sum\n",
    "            mp[c] = (i, j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        pre = [-1]*26\n",
    "        now = [-1]*26\n",
    "        ans = 0\n",
    "        s = list(s)\n",
    "        for j in range(len(s)):\n",
    "            c = s[j]\n",
    "            i = ord(c) - ord('A')\n",
    "            #print(c,now[i],pre[i])\n",
    "            if now[i] == -1:\n",
    "                now[i] = j\n",
    "            else:\n",
    "                ans += (j - now[i]) * (now[i] - pre[i])\n",
    "                pre[i] = now[i]\n",
    "                now[i] = j\n",
    "        n = len(s)\n",
    "        \n",
    "        for i in range(26):\n",
    "            if now[i] != -1:\n",
    "                ans += (n - now[i])*(now[i]-pre[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left = [1]*len(s)\n",
    "        right = [1]*len(s)\n",
    "        d = {s[0]:0}\n",
    "        for i in range(1, n):\n",
    "            if s[i] in d:\n",
    "                left[i] = i-d[s[i]]\n",
    "            else:\n",
    "                left[i] = i+1\n",
    "            d[s[i]] = i\n",
    "        d = {s[-1]:(n-1)}\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if s[i] in d:\n",
    "                right[i] = d[s[i]]-i\n",
    "            else:\n",
    "                right[i] = n-i\n",
    "            d[s[i]] = i\n",
    "        ans = sum(l*r for l, r in zip(left, right))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        '''\n",
    "        n, dct = len(s), defaultdict(list)\n",
    "        for i, c in enumerate(s): dct[c].append(i)\n",
    "        #print(dct)\n",
    "        ans = 0\n",
    "        for v in dct.values():\n",
    "            v = [-1] + v + [n]\n",
    "            #print(v)\n",
    "            for i in range(1, len(v) - 1):\n",
    "                ans += (v[i] - v[i - 1]) * (v[i + 1] - v[i])\n",
    "        return ans\n",
    "        '''\n",
    "        n, dct = len(s), defaultdict(list)\n",
    "        for i, c in enumerate(s): dct[c].append(i)\n",
    "        return sum((v[i] - (-1 if i == 0 else v[i - 1])) * ((n if i == len(v) - 1 else v[i + 1]) - v[i]) for v in dct.values() for i in range(len(v)))        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        pos = [[-1, -1] for _ in range(26)]\n",
    "        n = len(s)\n",
    "        dp = [0] * n\n",
    "        dp[0] = 1\n",
    "        pos[ord(s[0]) - ord('A')][1] = 0\n",
    "        for i, c in enumerate(s[1:], 1):\n",
    "            p = ord(c) - ord('A')\n",
    "            dp[i] = dp[i - 1] + (i - pos[p][1]) - (pos[p][1] - pos[p][0])\n",
    "            pos[p][0],  pos[p][1] = pos[p][1], i\n",
    "        return sum(dp)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int: \n",
    "        n = len(s)\n",
    "        f = [0] * n\n",
    "        last0, last1 = {}, {}\n",
    "        for i, c in enumerate(s):\n",
    "            p0, p1 = last0.get(c, -1), last1.get(c, -1)\n",
    "            f[i] = f[i - 1] + i - 2 * p0 + p1\n",
    "            last1[c] = last0.get(c, -1)\n",
    "            last0[c] = i\n",
    "        return sum(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        idx = defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            idx[c].append(i) # 记录字符每次出现的位置\n",
    "        res = 0\n",
    "        for c, arr in idx.items():\n",
    "            arr = [-1] + arr + [len(s)]\n",
    "            # print(f\"c:{c}, arr:{arr}\")\n",
    "            for i in range(1, len(arr) - 1):\n",
    "                res += (arr[i] - arr[i-1]) * (arr[i+1] - arr[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "\n",
    "        ans = ss = 0\n",
    "        d = defaultdict(list)\n",
    "\n",
    "        for i, ch in enumerate(s):\n",
    "            t = d[ch]\n",
    "            if not t:\n",
    "                ss += i + 1\n",
    "                t.append(-1)\n",
    "            else:\n",
    "                ss -= t[-1] - t[-2]\n",
    "                ss += i - t[-1]\n",
    "            t.append(i)\n",
    "            ans += ss\n",
    "            # print(ss)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        cnt = collections.defaultdict(list)\n",
    "        for i, ch in enumerate(s):\n",
    "            cnt[ch].append(i)\n",
    "        res = 0\n",
    "        for v in cnt.values():\n",
    "            arr = [-1] + v + [len(s)]\n",
    "            for i in range(1, len(arr)-1):\n",
    "                res += (arr[i]-arr[i-1])*(arr[i+1]-arr[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        post = defaultdict(list)\n",
    "        for index, item in enumerate(s):\n",
    "            post[item].append(index)\n",
    "        \n",
    "        res = 0\n",
    "        for indexed in post.values():\n",
    "            l = [-1] + indexed + [len(s)]\n",
    "            for index in range(1, len(l) - 1):\n",
    "                left = l[index - 1]\n",
    "                right = l[index + 1]\n",
    "                cur = l[index]\n",
    "                res += (right - cur) * (cur - left)\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dic = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            dic[s[i]].append(i)\n",
    "        res = 0\n",
    "        # mod = 10 ** 9 + 7\n",
    "        for c in dic:\n",
    "            for i in range(len(dic[c])):\n",
    "                l = dic[c][i - 1] if i > 0 else - 1\n",
    "                r = dic[c][i + 1] if i < len(dic[c]) - 1 else n\n",
    "                res += (dic[c][i] - l) * (r - dic[c][i])\n",
    "                # res %= mod\n",
    "        return res\n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        cnt=defaultdict(list)\n",
    "        for i,c in enumerate(s):\n",
    "            cnt[c].append(i)\n",
    "\n",
    "        res=0\n",
    "        for v in cnt.values():\n",
    "            v=[-1]+v+[len(s)]\n",
    "            for i in range(1,len(v)-1):\n",
    "                res +=(v[i]-v[i-1])*(v[i+1]-v[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        # 唯一字符的个数\n",
    "        # 每个位置左右两边的元素个数\n",
    "\n",
    "        dic = defaultdict(list)\n",
    "        for i,c in enumerate(s):\n",
    "            dic[c].append(i)\n",
    "        \n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        for i in dic:\n",
    "            arr = dic[i]\n",
    "\n",
    "            if len(arr) == 1:\n",
    "                res += (arr[0]+1)*(n-arr[0])\n",
    "                continue \n",
    "            for j in range(len(arr)):\n",
    "                if j == 0:\n",
    "                    res += (arr[j]+1)*(arr[j+1]-arr[j])\n",
    "                elif j == len(arr)-1:\n",
    "                    res += (arr[j] - arr[j-1])*(n-arr[j])\n",
    "                else:\n",
    "                    l, r = arr[j]-arr[j-1], arr[j+1]-arr[j]\n",
    "                    res += l*r\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self,s:str)->int:\n",
    "        pos={}\n",
    "        count={}\n",
    "        CapitalLetters='ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "        for i in CapitalLetters:\n",
    "            count[i]=0\n",
    "            pos[i]=[]\n",
    "            pos[i].append(0)\n",
    "            \n",
    "        j=0\n",
    "        for letter in s:\n",
    "            j+=1\n",
    "            count[s[j-1]]+=1\n",
    "            pos[s[j-1]].append(j)\n",
    "        for i in CapitalLetters:\n",
    "            count[i]+=1\n",
    "            pos[i].append(len(s)+1)\n",
    "        #print('lenth=%d'%len(s))\n",
    "        \n",
    "        total=0\n",
    "        for i in CapitalLetters:\n",
    "            #print('%c:'%i,end='')\n",
    "            for j in range(1,count[i]):\n",
    "                l=pos[i][j]-pos[i][j-1]-1\n",
    "                r=pos[i][j+1]-pos[i][j]-1\n",
    "                total+=(l+1)*(r+1)\n",
    "                #print('%d'%pos[i][j],end='\\t')\n",
    "            #print(list(pos[i]))\n",
    "            \n",
    "                \n",
    "        return int(total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dic = defaultdict(list)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if not dic[s[i]]:\n",
    "                dic[s[i]] = [-1, i, n]\n",
    "            else:\n",
    "                insort(dic[s[i]], i)\n",
    "        for v in dic.values():\n",
    "            l = len(v)\n",
    "            for i in range(1, l-1):\n",
    "                res += (v[i] - v[i-1])*(v[i+1] - v[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        n, ans = len(s), 0\n",
    "        pos = [[] for _ in range(26)]\n",
    "        for i, l in enumerate(s):\n",
    "            idx = ord(l) - ord('A')\n",
    "            pos[idx].append(i)\n",
    "            if len(pos[idx]) > 2:\n",
    "                j0, j1, j2 = pos[idx][-3], pos[idx][-2], pos[idx][-1]\n",
    "                ans += (j1 - j0) * (j2 - j1)\n",
    "            elif len(pos[idx]) == 2: ans += (pos[idx][0] + 1) * (pos[idx][1] - pos[idx][0])\n",
    "        for idx in range(26):\n",
    "            if len(pos[idx]) > 1:\n",
    "                j0, j1, j2 = pos[idx][-2], pos[idx][-1], n\n",
    "                ans += (j1 - j0) * (j2 - j1)\n",
    "            elif len(pos[idx]) == 1: ans += (pos[idx][0] + 1) * (n - pos[idx][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dic = defaultdict(list)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            dic[s[i]].append(i)\n",
    "\n",
    "        for v in dic.values():\n",
    "            v = [-1] + v + [n]\n",
    "            l = len(v)\n",
    "            for i in range(1, l-1):\n",
    "                res += (v[i] - v[i-1])*(v[i+1] - v[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        res = 0\n",
    "        n = len(s)\n",
    "        pos = defaultdict(list)\n",
    "\n",
    "        for i,letter in enumerate(s):\n",
    "            pos[letter].append(i)\n",
    "        for key, pos in pos.items():\n",
    "            pos.insert(0, -1)\n",
    "            pos.append(n)\n",
    "            m = len(pos)\n",
    "            for i in range(1, m-1):\n",
    "                res += (pos[i]-pos[i-1])*(pos[i+1]-pos[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self,s:str)->int:\n",
    "        pos={}\n",
    "        count={}\n",
    "        CapitalLetters='ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "        for i in CapitalLetters:\n",
    "            count[i]=0\n",
    "            pos[i]=[]\n",
    "            pos[i].append(0)\n",
    "            \n",
    "        j=0\n",
    "        for letter in s:\n",
    "            j+=1\n",
    "            count[s[j-1]]+=1\n",
    "            pos[s[j-1]].append(j)\n",
    "        for i in CapitalLetters:\n",
    "            count[i]+=1\n",
    "            pos[i].append(len(s)+1)\n",
    "        #print('lenth=%d'%len(s))\n",
    "        \n",
    "        total=0\n",
    "        for i in CapitalLetters:\n",
    "            #print('%c:'%i,end='')\n",
    "            for j in range(1,count[i]):\n",
    "                l=pos[i][j]-pos[i][j-1]-1\n",
    "                r=pos[i][j+1]-pos[i][j]-1\n",
    "                total+=(l+1)*(r+1)\n",
    "                #print('%d'%pos[i][j],end='\\t')\n",
    "            #print(list(pos[i]))\n",
    "            \n",
    "                \n",
    "        return int(total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        n, ans = len(s), 0\n",
    "        pos = [[] for _ in range(26)]\n",
    "        for i, l in enumerate(s):\n",
    "            idx = ord(l) - ord('A')\n",
    "            pos[idx].append(i)\n",
    "            if len(pos[idx]) > 2:\n",
    "                j0, j1, j2 = pos[idx][-3], pos[idx][-2], pos[idx][-1]\n",
    "                ans += (j1 - j0) * (j2 - j1)\n",
    "            elif len(pos[idx]) == 2: ans += (pos[idx][0] + 1) * (pos[idx][1] - pos[idx][0])\n",
    "        for idx in range(26):\n",
    "            if len(pos[idx]) > 1:\n",
    "                j0, j1, j2 = pos[idx][-2], pos[idx][-1], n\n",
    "                ans += (j1 - j0) * (j2 - j1)\n",
    "            elif len(pos[idx]) == 1: ans += (pos[idx][0] + 1) * (n - pos[idx][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        dic = collections.defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            dic[c].append(i)\n",
    "\n",
    "        res = 0\n",
    "        n = len(s)\n",
    "        # 只需对每个字符，计算有多少子字符串仅包含该字符一次即可.\n",
    "        # 对于每个出现的i index of ch\n",
    "        for arr in dic.values(): # arr is a list of index for each ch\n",
    "            arr = [-1] + arr + [n]\n",
    "            for i in range(1, len(arr)-1):\n",
    "                # arr[i-1]同字符上一次出现的位置, arr[i+1]下一次出现的位置为\n",
    "                res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i])\n",
    "        return res\n",
    "\n",
    "\"\"\"\n",
    "当它在某个子字符串中仅出现一次时，它会对这个子字符串统计唯一字符时有贡献。只需对每个字符，计算有多少子字符串仅包含该字符一次即可\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        index = collections.defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            index[c].append(i)\n",
    "\n",
    "        res = 0\n",
    "        for arr in index.values():\n",
    "            arr = [-1] + arr + [len(s)]\n",
    "            for i in range(1, len(arr) - 1):\n",
    "                res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        pos = defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            pos[c].append(i)\n",
    "        res = 0\n",
    "        for arr in pos.values():\n",
    "            arr = [-1] + arr + [len(s)]\n",
    "            for i in range(1, len(arr) - 1):\n",
    "                res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i])\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for i,e in enumerate(s):\n",
    "            d[e].append(i)\n",
    "        \n",
    "        ans = 0\n",
    "        for a in d.values():\n",
    "            a = [-1] + a + [len(s)]\n",
    "            for i in range(1,len(a) - 1):\n",
    "                ans += (a[i] - a[i - 1]) * (a[i + 1] - a[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        d={}\n",
    "        sum_g=0\n",
    "        ans=0\n",
    "        for i,x in enumerate(s):\n",
    "            if x not in d:\n",
    "                sum_g+=(i+1)\n",
    "                d[x]=[-1]\n",
    "                d[x].append(i)\n",
    "            else:\n",
    "                sum_g=sum_g+(i-d[x][-1])-(d[x][-1]-d[x][-2])\n",
    "                d[x].append(i)\n",
    "            \n",
    "            ans+=sum_g\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        index = collections.defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            index[c].append(i)\n",
    "\n",
    "        res = 0\n",
    "        # 例如字符串为'ABCBD',index['B'] = [1,3]\n",
    "        for arr in index.values():\n",
    "            arr = [-1] + arr + [len(s)] # arr = [-1,1,3,5]\n",
    "            for i in range(1, len(arr) - 1):\n",
    "                res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        chardict = {}\n",
    "        lens = len(s)\n",
    "        for i, item in enumerate(s):\n",
    "            if item not in chardict:\n",
    "                chardict[item] = []\n",
    "            chardict[item].append(i)\n",
    "        ans = 0\n",
    "        for i, item in enumerate(s):\n",
    "            slist = chardict[item]\n",
    "            idx = bisect_left(slist, i)\n",
    "            l = r = 0\n",
    "            if idx == 0:\n",
    "                l = i + 1\n",
    "            else:\n",
    "                l = i - slist[idx-1]\n",
    "            if idx + 1 >= len(slist):\n",
    "                r = lens - i\n",
    "            else:\n",
    "                r = slist[idx+1] - i\n",
    "            ans += l*r\n",
    "            # print(slist, idx, l, r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        d = {}\n",
    "        ans=0\n",
    "        n=len(s)\n",
    "        for i,c in enumerate(s):\n",
    "            if c not in d:\n",
    "                d[c]=[-1,i]\n",
    "            else:\n",
    "                a,b = d[c][-2],d[c][-1]\n",
    "                ans += (b-a)*(i-b)\n",
    "                d[c].append(i)\n",
    "        for c in d:\n",
    "            a,b = d[c][-2],d[c][-1]\n",
    "            ans += (b-a)*(n-b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# consider a substring ACBBEA.\r\n",
    "# the first A will be effective as unique in: A\r\n",
    "# the second A will be effective as unique in: CBBEA BBEA BEA A\r\n",
    "# an appearance of each letter is count idx - prev idx of same letter times\r\n",
    "class Solution:\r\n",
    "    def uniqueLetterString(self, s: str) -> int:\r\n",
    "        index = collections.defaultdict(list)\r\n",
    "        for i, c in enumerate(s):\r\n",
    "            index[c].append(i)\r\n",
    "\r\n",
    "        res = 0\r\n",
    "        for arr in index.values():\r\n",
    "            arr = [-1] + arr + [len(s)]\r\n",
    "            for i in range(1, len(arr) - 1):\r\n",
    "                res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i])\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        '''\n",
    "        n, dct = len(s), defaultdict(list)\n",
    "        for i, c in enumerate(s): dct[c].append(i)\n",
    "        #print(dct)\n",
    "        ans = 0\n",
    "        for v in dct.values():\n",
    "            v = [-1] + v + [n]\n",
    "            #print(v)\n",
    "            for i in range(1, len(v) - 1):\n",
    "                ans += (v[i] - v[i - 1]) * (v[i + 1] - v[i])\n",
    "        return ans\n",
    "        '''\n",
    "        n, dct = len(s), defaultdict(list)\n",
    "        for i, c in enumerate(s): dct[c].append(i)\n",
    "        return sum((v[i] - (-1 if i == 0 else v[i - 1])) * ((n if i == len(v) - 1 else v[i + 1]) - v[i]) for v in dct.values() for i in range(len(v)))        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "\n",
    "\n",
    "        \n",
    "        index = collections.defaultdict(list)\n",
    "\n",
    "\n",
    "        for i, c in enumerate(s):\n",
    "            index[c].append(i)\n",
    "\n",
    "        res = 0\n",
    "        for arr in index.values():\n",
    "\n",
    "\n",
    "            arr = [-1] + arr + [len(s)]\n",
    "\n",
    "\n",
    "            for i in range(1, len(arr) - 1):\n",
    "\n",
    "                res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        loc = collections.defaultdict(list)\n",
    "        for i, ch in enumerate(s):\n",
    "            loc[ch].append(i)\n",
    "        res, n = 0, len(s)\n",
    "        for A in loc.values():\n",
    "            A = [-1] + A + [n]\n",
    "            for i in range(1, len(A)-1):\n",
    "                res += (A[i] - A[i-1]) * (A[i+1] - A[i])\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        index = collections.defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            index[c].append(i)\n",
    "\n",
    "        res = 0\n",
    "        for arr in index.values():\n",
    "            arr = [-1] + arr + [len(s)]\n",
    "            for i in range(1, len(arr) - 1):\n",
    "                res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "\n",
    "        \n",
    "        index = collections.defaultdict(list)\n",
    "\n",
    "        for i, c in enumerate(s):\n",
    "            index[c].append(i)\n",
    "\n",
    "        res = 0\n",
    "        for arr in index.values():\n",
    "            arr = [-1] + arr + [len(s)]\n",
    "\n",
    "            for i in range(1, len(arr) - 1):\n",
    "                res += ( arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        # def helper(s):\n",
    "        #     dic = {}\n",
    "        #     count = 0\n",
    "        #     for i in s:\n",
    "        #         dic[i] = dic.get(i,0)+ 1\n",
    "        #     for i in dic:\n",
    "        #         if dic[i] == 1:\n",
    "        #             count += 1\n",
    "        #     return count\n",
    "        # ziji = []\n",
    "        # l = len(s)\n",
    "        # for i in range(1,l+1):\n",
    "        #     for j in range(l-i+1):\n",
    "        #         ziji.append(s[j:j+i])\n",
    "        # res = 0\n",
    "        # for i in ziji:\n",
    "        #     res += helper(i)\n",
    "        # return res\n",
    "        dic = collections.defaultdict(list)\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            dic[s[i]].append(i)\n",
    "        \n",
    "        for index in list(dic.values()):\n",
    "            cur = [-1] + index + [n]\n",
    "            for i in range(1,len(cur)-1):\n",
    "                left = cur[i-1]\n",
    "                right = cur[i+1]\n",
    "                res += (cur[i]-left) * (right-cur[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self,s:str)->int:\n",
    "        pos=[]\n",
    "        count=[]\n",
    "        #CapitalLetters='ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "        for i in range(0,26):\n",
    "            count.append(0)\n",
    "            pos.append([])\n",
    "            pos[i].append(0)\n",
    "            \n",
    "        j=0\n",
    "        for letter in s:\n",
    "            j+=1\n",
    "            count[ord(s[j-1])-ord('A')]+=1\n",
    "            pos[ord(s[j-1])-ord('A')].append(j)\n",
    "        for i in range(0,26):\n",
    "            count[i]+=1\n",
    "            pos[i].append(len(s)+1)\n",
    "        #print('lenth=%d'%len(s))\n",
    "        \n",
    "        total=0\n",
    "        for i in range(0,26):\n",
    "            #print('%c:'%i,end='')\n",
    "            for j in range(1,count[i]):\n",
    "                l=pos[i][j]-pos[i][j-1]-1\n",
    "                r=pos[i][j+1]-pos[i][j]-1\n",
    "                total+=(l+1)*(r+1)\n",
    "                #print('%d'%pos[i][j],end='\\t')\n",
    "            #print(list(pos[i]))\n",
    "            \n",
    "                \n",
    "        return int(total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        index = defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            index[c].append(i)\n",
    "\n",
    "        res = 0\n",
    "        for arr in index.values():\n",
    "            arr = [-1] + arr + [len(s)]\n",
    "            for i in range(1, len(arr) - 1):\n",
    "                res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "\n",
    "        index = collections.defaultdict(list)\n",
    "\n",
    "        for i, c in enumerate(s):\n",
    "            index[c].append(i)\n",
    "\n",
    "        res = 0\n",
    "        for arr in index.values():\n",
    "\n",
    "            arr = [-1] + arr + [len(s)]\n",
    "\n",
    "            for i in range(1, len(arr) - 1):\n",
    "                res += ( arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i])\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def uniqueLetterString(self, s: str) -> int:\r\n",
    "        pos=[[-1] for _ in range(26)]\r\n",
    "        for i,c in enumerate(s):\r\n",
    "            pos[ord(c)-ord('A')].append(i)\r\n",
    "        ret=0\r\n",
    "        for ar in pos:\r\n",
    "            if len(ar)==1:\r\n",
    "                continue\r\n",
    "            ar.append(len(s))\r\n",
    "            for i in range(1,len(ar)-1):\r\n",
    "                ret+=(ar[i]-ar[i-1])*(ar[i+1]-ar[i])\r\n",
    "        return ret\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        index = collections.defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            index[c].append(i)\n",
    "\n",
    "        res = 0\n",
    "        for arr in index.values():\n",
    "            arr = [-1] + arr + [len(s)]\n",
    "            for i in range(1, len(arr) - 1):\n",
    "                res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        index = collections.defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            index[c].append(i)\n",
    "\n",
    "        res = 0\n",
    "        for arr in index.values():\n",
    "            arr = [-1] + arr + [len(s)]\n",
    "            for i in range(1, len(arr)-1):\n",
    "                res += (arr[i]-arr[i-1]) * (arr[i+1]-arr[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            d[c].append(i)\n",
    "        ans = 0\n",
    "        for v in d.values():\n",
    "            cur = [-1] + v + [len(s)]\n",
    "            for i in range(1, len(cur) - 1):\n",
    "                ans += (cur[i] - cur[i - 1]) * (cur[i + 1] - cur[i])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "\n",
    "\n",
    "        index = collections.defaultdict(list)\n",
    "\n",
    "        for i, c in enumerate(s):\n",
    "            index[c].append(i)\n",
    "\n",
    "        res = 0\n",
    "        for arr in index.values():\n",
    "\n",
    "            arr = [-1] + arr + [len(s)]\n",
    "\n",
    "            for i in range(1, len(arr) - 1):\n",
    "                res += ( arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i])\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "\n",
    "        \n",
    "        index = collections.defaultdict(list)\n",
    "\n",
    "        for i, c in enumerate(s):\n",
    "            index[c].append(i)\n",
    "\n",
    "        res = 0\n",
    "        for arr in index.values():\n",
    "            arr = [-1] + arr + [len(s)]\n",
    "\n",
    "            for i in range(1, len(arr) - 1):\n",
    "                res += ( arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        n, mp, ans = len(s), {}, 0\n",
    "        for i in range(n):\n",
    "            if s[i] not in mp:\n",
    "                mp[s[i]] = []\n",
    "            mp[s[i]].append(i)\n",
    "        for k, v in mp.items():\n",
    "            l = len(v)\n",
    "            v = [-1] + v + [n]\n",
    "            for t in range(1, l + 1):\n",
    "                ans += (v[t] - v[t - 1]) * (v[t + 1] - v[t])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, s: str) -> int:\n",
    "        c = defaultdict(list)\n",
    "        n = len(s)\n",
    "        dp = [0] * (n)\n",
    "        dp[0] = 1\n",
    "        c[s[0]] = [0]\n",
    "        for i in range(1, n):\n",
    "            if len(c[s[i]]) == 0:\n",
    "                dp[i] = dp[i - 1] + i + 1\n",
    "                c[s[i]].append(i)\n",
    "            elif len(c[s[i]]) == 1:\n",
    "                dp[i] = dp[i - 1] + i + 1 - 2 * (c[s[i]][0] + 1)\n",
    "                c[s[i]].append(c[s[i]][0])\n",
    "                c[s[i]][0] = i\n",
    "            else:\n",
    "                dp[i] = dp[i - 1] + i + 1 - 2 * (c[s[i]][0] - c[s[i]][1]) - c[s[i]][1] - 1 \n",
    "                c[s[i]][1] = c[s[i]][0]\n",
    "                c[s[i]][0] = i\n",
    "        print(dp)\n",
    "        return sum(dp)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
